package com.zlk.algorithm.dataStructure.linkList03;

import java.util.HashMap;

/**
 * @program: algorithm
 * @ClassName CopyRandLinkList
 * @description:
 *     https://leetcode.cn/problems/copy-list-with-random-pointer/
 * @author: slfang
 * @create: 2024-02-01 16:38
 * @Version 1.0
 **/
public class Code09_CopyRandLinkList {

    public class Node {
        public int val;
        public Node next;
        public Node random;
        Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    // 方法1 hash表
    // 不用额外空间，先构造一个copy节点再原节点的next 节点的链表
    // 然后依次拿出 原节点和复制节点 作用是替代哈希表的作用
    // 设置copy 的random
    // 然后分离链表
    //
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;

        //1、复制节点挂在老节点后面
        while (cur != null) {
            Node cNext = cur.next;
            Node copy = new Node(cur.val);
            cur.next = copy;
            copy.next = cNext;
            cur = cNext;
        }
        //2、
        //设置random
        cur = head;
        while (cur!=null){

            Node copyNode = cur.next;
            Node random = cur.random;
            Node cRandom = random!=null?random.next:null;
            copyNode.random = cRandom;
            cur = copyNode.next;
        }

        cur = head;
        Node copyHead = cur.next;
        Node curCopy = copyHead;
        while (cur!=null){
            curCopy = cur.next;
            Node next = cur.next.next;
            cur.next = next;
            curCopy.next = next==null?null:next.next;
            cur = next;
        }
        return copyHead;

    }






}
